package code;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;


public class WordBreak {
	
	 public boolean wordBreak(String s, Set<String> dict) {
	        Iterator<String> it = dict.iterator();
	        int n=s.length();
	        boolean[] dp=new boolean[n+1];
	        String subStr;
	        /*
	         * dp[i]表示0~i是否能组成单词
	         * dp[i]由dp[j]与[j...i]一起决定j<=i
	         */
	        for(int i=1;i<=n;i++){
	        	dp[i]=false;
	        	for(int j=0;j<i;j++){
	        		//subString(j,i)只能取到[j...i-1]的字符
	        		subStr=s.substring(j, i);
	        		if(dict.contains(subStr)){
	        			//[j...i]能组成单词的话，那么dp[j][i]=|dp[j-1][i]
	        			if(j==0 || dp[j]){
	        				dp[i]=true;
	        				break;
	        			}
	        		}
	        	}
	        	
	        }
	        if(dp[n])	return true;
	        return false;
	    }
	 public static void main(String[] args){
		 WordBreak wb=new WordBreak();
		 String s="ab";
		 Set set=new HashSet<String>();
		 set.add("a");
		 set.add("b");
		 System.out.println(wb.wordBreak(s, set));
	 }
}
